/*
 * Quercia Luciano
 * Algoritmi e Strutture Dati
 * a.a. 2009-10
 */


#ifndef GRAFO_H_
#define GRAFO_H_

//#define NDEBUG
#include <cassert>

#include "nodoG.h"
#include "lista/lista.h"

template <class T>
class Grafo {

public:
	Grafo();
	~Grafo();


	typedef NodoG<T> * nodo;

	void creaGrafo();
	bool grafoVuoto();
	void insNodo( nodo )		throw (char const *) ;
	void insArco( nodo, nodo )	throw (char const *) ;
	void cancNodo( nodo )		throw (char const *) ;
	void cancArco( nodo, nodo )	throw (char const *) ;
	bool esisteNodo( nodo )		throw (char const *) ;
	bool esisteArco(nodo,nodo)	throw (char const *) ;
	Lista<nodo> adiacenti(nodo)	throw (char const *) ;
	T leggiNodo( nodo ) 		throw (char const *) ;
	void scrivinodo( nodo, T) 	throw (char const *) ;

	//personalizzati
	bool esisteNodo( T );
	nodo creaNodo( T );

private:

	typedef NodoG<T> cella;
	typedef typename Lista< cella >::posizione index;
	typedef typename Lista< nodo >::posizione indexPtr;

	Lista< cella > nodi;
	int nNodi;
};

template<class T>
Grafo<T>::Grafo() {
	creaGrafo();
}


template<class T>
Grafo<T>::~Grafo() {
	nodi.~Lista();
	nNodi = 0;
}


template<class T>
void Grafo<T>::creaGrafo() {
	nNodi = 0;
}


template<class T>
bool Grafo<T>::grafoVuoto() {
	return nNodi == 0;
}


template<class T>
void Grafo<T>::insNodo( nodo n ) throw (char const *) {
	if ( !esisteNodo( n ) ) {
		index p;
		p = nodi.primoLista();

		nodi.insLista( *n , p);
		nNodi++;
	} else
		throw "Il nodo esiste già.";
}


template<class T>
void Grafo<T>::insArco(nodo n1, nodo n2) throw (char const *) {
	if ( esisteNodo( n1 ) )
		if ( esisteNodo( n2 ) ) {
			index p = nodi.primoLista();
			while ( ! nodi.fineLista(p) ) {
				if ( nodi.leggiLista(p) == *n1 )
					break;
				p = nodi.succLista(p);
			}
			assert( p->getValue() == n1->getValue() );
			n1->insAdiacente( n2 );
		}
		else
			throw "Il nodo 2 non esiste.";
	else
		throw "Il nodo 1 non esiste.";
}



template<class T>
void Grafo<T>::cancNodo(nodo n1) throw (char const *) {
	if ( esisteNodo(n1) )
		if ( adiacenti(n1).listaVuota() ) {
			//cancella
			index p = nodi.primoLista();
			while ( !nodi.fineLista(p) ) {
				if ( nodi.leggiLista(p) == *n1 )
					break;
				p = nodi.succLista(p);
			}
			assert( ! nodi.fineLista(p) );
			nodi.cancLista( p );
			nNodi--;
		}
		else
			throw "Nodo connesso ad altri. Impossibile rimuovere.";
	else
		throw "Il nodo non esiste.";
}



template<class T>
void Grafo<T>::cancArco(nodo n1, nodo n2) throw (char const *) {
	if ( esisteNodo(n1) )
		if ( esisteNodo(n2) )
			if ( esisteArco(n1, n2) )
				n1->cancAdiacente( n2 );
			else
				throw "L'arco non esiste.";
		else
			throw "Il secondo nodo non esiste.";
	else
		throw "Il primo nodo non esiste.";
}



template<class T>
bool Grafo<T>::esisteNodo(nodo n) throw (char const *) {
	index p = nodi.primoLista();
	while ( !nodi.fineLista(p) ) {
		if ( nodi.leggiLista(p) == *n )
			return true;
		p = nodi.succLista( p );
	}
	return false;
}



template<class T>
bool Grafo<T>::esisteArco(nodo n1, nodo n2) throw (char const *) {
	if ( esisteNodo( n1 ) )
		if ( esisteNodo( n2 ) ) {

			//verifico se c'è n2 trai suoi adiacenti
			Lista<nodo> l = adiacenti( n1 );

			indexPtr q = l.primoLista();
			while ( ! l.fineLista(q) ) {
				if ( l.leggiLista(q) == n2 )
					return true;
				q = l.succLista(q);
			}
			return false;
		}
		else
			throw "Il nodo 2 non esiste.";
	else
		throw "Il nodo 1 non esiste.";
}



template<class T>
Lista<typename Grafo<T>::nodo> Grafo<T>::adiacenti(nodo n)
throw (char const *) {
	return n->getList();
}



template<class T>
T Grafo<T>::leggiNodo(nodo n) throw (char const *) {
	if ( n != NULL )
		if ( esisteNodo(n) )
			return n->getValue();
		else
			throw "Il nodo non esiste.";
	else
		throw "Nodo non valido";
}



template<class T>
void Grafo<T>::scrivinodo(nodo n, T elem) throw (char const *) {
	if ( n!=NULL )
		if ( esisteNodo(n) )
			n->setValue( elem );
		else
			throw "Il nodo non esiste.";
	else
		throw "Nodo non valido";
}




template<class T>
bool Grafo<T>::esisteNodo( T elem ) {
	index p = nodi.primoLista();

	while ( !nodi.fineLista(p) ) {
		if ( nodi.leggiLista(p).getValue() == elem )
			return true;
		p = nodi.succLista( p );
	}
	return false;
}


template<class T>
typename Grafo<T>::nodo Grafo<T>::creaNodo( T elem ) {
	return ( new cella( elem ) );
}


#endif /* GRAFO_H_ */
